using System.Text;

/// <summary>
/// 顺序表
/// </summary>
/// <typeparam name="T"></typeparam>
public class SeqList<T> : IListDS<T>
{
    public SeqList() { }
    public SeqList(int size)
    {
        Data = new T[size];
        MaxSize = size;
        Last = -1;
    }
    /// <summary>
    /// 顺序表的容量 
    /// 不代表索引
    /// </summary>
    /// <value></value>
    public int MaxSize { get; set; }
    /// <summary>
    /// 数组，用于存储顺序表中的数据元素
    /// </summary>
    /// <value></value>
    public T[]? Data { get; set; }
    /// <summary>
    /// 指向顺序表的最后一个元素
    /// 代表索引而不是第几个元素
    /// </summary>
    /// <value></value>
    public int Last { get; set; }
    /// <summary>
    /// 索引器
    /// </summary>
    /// <value></value>
    public T this[int index]
    {
        get
        {
            return Data == null ? default(T) : Data[index];
        }
        set
        {
            Data[index] = value;
        }
    }
    public void Append(T item)
    {
        if (IsFull())
        {
            System.Console.WriteLine("表满");
            return;
        }
        Data[++Last] = item;
    }

    /// <summary>
    /// 清空
    /// </summary>
    public void Clear() => Last = -1;

    /// <summary>
    /// 删除第i个元素
    /// </summary>
    /// <param name="i">待删除元素的位置</param>
    /// <returns></returns>
    public T Delete(int i)
    {
        T temp = default(T);
        //判断表是否空
        if (IsEmpty())
        {
            System.Console.WriteLine("表空");
            return temp;
        }

        //判断位置是否合法，i取值范围在[1,Last+1]
        if (i < 1 || i > Last + 1)
        {
            System.Console.WriteLine("位置错误");
            return temp;
        }
        if (i == Last + 1)
        {
            temp = Data[Last];
        }
        else
        {
            temp = Data[i - 1];
            for (int j = i; j < Last + 1; j++)
            {
                Data[j - 1] = Data[j];
            }
        }
        //修改表长
        --Last;
        return temp;
    }

    /// <summary>
    /// 取第i个位置的表元素
    /// </summary>
    /// <param name="i">第几个</param>
    /// <returns></returns>
    public T GetElem(int i)
    {
        if (IsEmpty())
        {
            System.Console.WriteLine("表空");
            return default(T);
        }
        if (i < 1 || i > Last + 1)
        {
            System.Console.WriteLine("位置错误");
            return default(T);
        }
        return Data[i - 1];
    }

    /// <summary>
    /// 求表长
    /// </summary>
    /// <returns></returns>
    public int GetLength() => Last + 1;

    /// <summary>
    /// 插入
    /// 将某个数据插入到第i个位置，将顺序表元素ai~an（插入前第i个位置以及i之后的元素）依次向后移动，
    /// 为待插入数据提供位置
    /// </summary>
    /// <param name="item">待插入的元素</param>
    /// <param name="i">插入位置</param>
    public void Insert(T item, int i)
    {
        //1.判断是否满
        if (IsFull())
        {
            System.Console.WriteLine("表满");
            return;
        }
        //2.判断插入位置是否合法
        //i代表插入位置，注意不是索引，i的值必须大于等于1
        //Last是指向列表最后一个元素的位置索引！Last+1标识最后一个元素的位置
        //Last+2表示在顺序表的最后一个元素之后插入
        //因为顺序表存储是连续的，所以，i的取值区间为[1,Last+2] 
        if (i < 1 || i > Last + 2)
        {
            System.Console.WriteLine("位置有误");
            return;
        }
        //如果在顺序表的最后一个元素之后插入
        if (i == Last + 2)
        {
            //直接赋值，不需要元素右移
            Data[i - 1] = item;
        }
        //在表其他位置插入
        else
        {
            //从最后一个元素开始右移 必须  否则会造成元素覆盖丢失
            for (int j = Last; j >= i - 1; --j)
            {
                //从后至前依次右移一个位置
                Data[j + 1] = Data[j];
            }
            //for执行完毕后，把新元素插入到第i个位置上
            Data[i - 1] = item;
        }
        //不要忘记修改表长
        Last++;
    }

    /// <summary>
    /// 判空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty() => Last == -1;

    /// <summary>
    /// 根据给定的元素定位，
    /// </summary>
    /// <param name="value">元素的索引值</param>
    /// <returns></returns>
    public int Locate(T value)
    {
        if (IsEmpty())
        {
            System.Console.WriteLine("表空");
            return -1;
        }
        int i = 0;//标记索引
        //从左至右查找
        for (i = 0; i < Last + 1; i++)
        {
            //如果找到了  ，直接跳出循环
            if (value.Equals(Data[i]))
            {
                break;
            }
        }
        //如果i>Last，说明找完了整个表，但没有元素与要定位的元素值相等，返回-1，否则返回索引
        return i > Last ? -1 : i;
    }

    /// <summary>
    /// 判表满
    /// </summary>
    /// <returns></returns>
    public bool IsFull() => Last == MaxSize - 1;

    /// <summary>
    /// 重写个ToString
    /// </summary>
    /// <returns></returns>
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < Last + 1; i++)
        {
            sb.Append($"[{Data[i]}],");
        }
        if (sb.Length == 0)
        {
            return string.Empty;
        }
        string str = sb.ToString();

        str = str.TrimEnd(',');
        return str;
    }
}